import javafx.util.Pair;

public class MyBTree {
    static class BTRNode{
        public int[] keys;
        public BTRNode[] subs;
        public BTRNode parent;
        public int usedSize;

        public BTRNode(){
            // 为了方便分裂，需多开辟一个空间
            this.keys = new int[M];
            this.subs = new BTRNode[M + 1];
            this.usedSize = 0;
            this.parent = null;
        }
    }

    public static final int M = 3;
    public BTRNode root;

    public boolean insert(int key){
        // 1. 插入之前要先判断 B 树是否为空
        if(this.root == null){
            BTRNode node = new BTRNode();
            node.keys[0] = key;
            node.usedSize++;
            this.root = node;
            return true;
        }
        // 2. 插入之前要先在 B 树中找，看 key 是否存在
        Pair<BTRNode, Integer> ret = findKey(key);
        // 3. 如果找到了 key，就不用再插入了
        if(ret.getValue() != -1){
            return false;
        }
        // 4. 如果没找到 key，需要进行插入
        BTRNode cur = ret.getKey();
        int i = cur.usedSize - 1;
        for( ; i >= 0; i--){
            if(cur.keys[i] >= key){
                cur.keys[i + 1] = cur.keys[i];
            }else{
                break;
            }
        }
        cur.keys[i + 1] = key;
        cur.usedSize++;
        // 5. 如果插入后的 cur.usedSize >= M - 1，需要进行分裂
        if(cur.usedSize >= M){
            split(cur);
            return true;
        }else{
            return true;
        }
    }

    private void split(BTRNode cur) {
        // 创建一个新的节点 - 放在右边
        BTRNode newNode = new BTRNode();
        // 将原来节点的一半值移到新节点中
        int mid = cur.usedSize / 2;
        int i = mid + 1;
        int j = 0;

        for( ; i < cur.usedSize; i++){
            // 不仅要移动 key 值，还要移动它的孩子节点
            newNode.keys[j] = cur.keys[i];
            newNode.subs[j] = cur.subs[i];
            // 处理刚拷贝过来的孩子节点的父亲节点
            if(cur.subs[i] != null){
                cur.subs[i].parent = newNode;
            }
            j++;
        }
        newNode.subs[j] = cur.subs[i];
        if(cur.subs[i] != null){
            cur.subs[i].parent = newNode;
        }
        // 更新 newNode, cur 的 usedSize
        newNode.usedSize = j;
        cur.usedSize = mid;

        // 处理分裂根节点的情况
        if(cur == root){
            BTRNode newRoot = new BTRNode();
            newRoot.keys[0] = cur.keys[mid];
            newRoot.subs[0] = cur;
            cur.parent = newRoot;
            newRoot.subs[1] = newNode;
            newNode.parent = newRoot;
            newRoot.usedSize = 1;
            root = newRoot;
            return;
        }

        // 如果分裂的 cur 节点不是根节点
        BTRNode parent = cur.parent;
        // 将节点的 mid 位置的值，移动向父节点
        int pIndex = parent.usedSize - 1;
        for( ; pIndex >= 0; pIndex--){
            if(parent.keys[pIndex] >= cur.keys[mid]){
                // 不仅要移动 key，还要移动子节点
                parent.keys[pIndex + 1] = parent.keys[pIndex];
                parent.subs[pIndex + 2] = parent.subs[pIndex + 1];
            }else{
                break;
            }
        }
        parent.keys[pIndex + 1] = cur.keys[mid];

        newNode.parent = parent;
        parent.subs[pIndex + 2] = newNode;
        // 更新 parent 的 usedSize
        parent.usedSize++;

        if(parent.usedSize >= M){
            split(parent);
        }
    }

    private Pair<BTRNode, Integer> findKey(int key) {
        BTRNode cur = root;
        BTRNode parent = null;
        while(cur != null){
            int index = 0;
            while(index < cur.usedSize){
                if(cur.keys[index] < key){
                    index++;
                }else if(cur.keys[index] > key){
                    break;
                }else{
                    return new Pair<>(cur, index);
                }
            }
            parent = cur;
            cur = cur.subs[index];
        }
        return new Pair<>(parent, -1);
    }

    public static void main(String[] args) {
        MyBTree myBTree = new MyBTree();
        int[] array = {53, 139, 75, 49, 145, 36, 101};

        for(int i = 0; i < array.length; i++){
            myBTree.insert(array[i]);
        }

        System.out.println();
    }
}
